package com.LeeCode;

/**
 * 打家劫舍 IV
 */

public class Code2560 {
    public static void main(String[] args) {
        int[] nums = {2, 3, 5, 9};
        int k = 2;
        System.out.println(new Code2560().minCapability(nums, k));
    }

    public int minCapability(int[] nums, int k) {
        int left = 0, right = 0;
        for (int num : nums) {
            right = Math.max(right, num);
        }
        while ((left + 1 < right)) {
            int mid = left + (right - left) / 2;
            if (check(nums, k, mid))
                right = mid;
            else
                left = mid;
        }
        return right;
    }

    private boolean check(int[] nums, int k, int limit) {
        int count = 0, index = 0;
        while (index < nums.length) {
            if (nums[index] <= limit) {
                count++;
                index += 2;
            } else {
                index++;
            }
            if (count >= k)
                return true;
        }
        return false;
    }
}
